1. Field of the Invention
The present invention relates to the field of computer systems. More specifically, the present invention relates to the art of instruction caching.
2. Background Information
Historically, cached instructions are stored and organized in an instruction cache in accordance with the instructions' spatial relationship. Typically, each cache line stores instructions that are located spatially adjacent to each other in main memory. This spatial approach to caching instructions has at least one disadvantage in that it typically requires multiple cache lines to be accessed whenever execution of a program necessitates branching out from the middle of a cache line or branching into the middle of a cache line.
In U.S. Pat. No. 5,381,533, Peleg and Weiser disclosed an alternative approach to organizing cached instructions that overcome the above discussed and other disadvantages of the spatial approach. Under Peleg and Weiser's approach, cached instructions are stored and organized in accordance with the predicted order of execution. Basic blocks of instructions that are predicted to be sequentially executed are organized into trace segments and stored in the cache lines, one trace segment per cache line. The successor basic blocks stored into a cache line to form a trace segment are the branch target basic blocks if the branch instructions located at the end of the corresponding predecessor basic blocks are predicted to be taken; otherwise the successor basic blocks are the fall through basic blocks. The successive basic blocks within a cache line are retrieved sequentially by way of the first instruction of the first basic block, upon locating the first instruction.
Because the Peleg and Weiser approach does not provide for trace segments to span multiple cache lines, address matching to locate the next cache line must be performed each time the instruction supply stored in a cache line is exhausted. As a result, the Peleg and Weiser approach has at least the disadvantage of being limiting in the amount of instructions that can be supplied to the execution units of a processor over a period of time. This limitation is especially undesirable for modern processors with very high instruction execution rates.
Melvin et al., in their article entitled Hardware Support for Large Atomic Units in Dynamically Scheduled Machines, Proceedings of the 21st Annual Workshop on Microprogramming and Microarchitecture, Nov. 30-Dec. 2, 1988, San Diego, Calif., have proposed storing and organizing cached instructions by execution atomic units. Each cache entry (presumably, a cache line) is to comprise an execution atomic unit. An execution atomic unit is a smallest group of micro-ops that the processor can issue as an indivisible unit. Micro-ops are micro-instructions employed by the processor to implement macro-instructions. A fill unit is proposed for building the execution atomic units. The fill unit is to receive the micro-ops from a pre-fetch buffer and micro-op generator. There are at least two conditions under which the building of an execution atomic unit would terminate. The first is when a change of flow control is detected, and the second is when there are no longer enough empty micro-op slots in the fill unit for the next macro-instruction.
The Melvin approach suffers from a number of disadvantages including at least the disadvantages of allowing basically only one basic block per atomic execution unit, and having to cache all decoded micro-ops of a macro instruction. The later is especially undesirable if the macro-instruction set includes complex macro-instructions that decode into a large number of micro-ops.
Thus, it is desirable to have a new approach for storing and organizing cached instructions, including decoded micro-ops, that has the advantages of Peleg et al., and Melvin et al., but without their disadvantages.